import java.util.*;

public class Solution {

    public static boolean checkInclusion(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        Map<Character, Integer> hash = new HashMap<>();
        for(int i = 0; i < n; i++){
            hash.put(s1.charAt(i), hash.getOrDefault(s1.charAt(i), 0) + 1);
        }

        for(int i = 0; i < m; i++){
            if(hash.containsKey(s2.charAt(i))){
                hash.put(s2.charAt(i), hash.getOrDefault(s2.charAt(i), 0) - 1);
                if(hash.get(s2.charAt(i)) == 0) { hash.remove(s2.charAt(i));}
            }
            if(i < n - 1) { continue;}
            if(hash.size() == 0) { return true;}
            if(hash.containsKey(s2.charAt(i - n + 1))){
                hash.put(s2.charAt(i - n + 1), hash.getOrDefault(s2.charAt(i - n + 1), 0) + 1);
            }
        }
        return false;
    }

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        int n = s.length(), m = p.length();
        if(n < m) { return ret;}

        int[] cur = new int[26];
        for(int i = 0; i < m; i++) {
            cur[p.charAt(i) - 'a']++;
        }
        int[] count = new int[26];
        for(int i = 0; i < m; i++){
            count[s.charAt(i) - 'a']++;
        }
        if(check(cur, count)) { ret.add(0);}

        for(int i = m; i < n; i++){
            count[s.charAt(i) - 'a']++;
            count[s.charAt(i - m) - 'a']--;
            if(check(cur, count)) { ret.add(i - m + 1);}
        }
        return ret;
    }

    public List<Integer> findAnagrams2(String s, String p) {
        int n = s.length(), m = p.length();
        List<Integer> ret = new ArrayList<>();
        int[] c1 = new int[26];
        int[] c2 = new int[26];
        for(int i = 0; i < m; i++){
            c2[p.charAt(i) - 'a']++;
        }

        int count = 0;
        for(int left = 0, right = 0; right < n; right++){
            c1[s.charAt(right) - 'a']++;
            if(c1[s.charAt(right) - 'a'] <= c2[s.charAt(right) - 'a']){
                count++;
            }
            if(right - left + 1 > m){
                char tmp = s.charAt(left++);
                if(c1[tmp - 'a'] <= c2[tmp - 'a']){
                    count--;
                }
                c1[tmp - 'a']--;
            }
            if(m == count) { ret.add(left);}
        }
        return ret;
    }

    public boolean check(int[] c1, int[] c2){
        for(int i = 0; i < 26; i++){
            if(c1[i] != c2[i]) { return false;}
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(checkInclusion("ab", "eidboaoo"));
    }
}
